/*
题目链接 : 
https://leetcode.cn/problems/choose-k-elements-with-maximum-sum/?slug=fruits-into-baskets-ii&tab=solutions&tab=3603047&tab=mei-ju-zuo-duan-dian-wei-hu-zui-xiao-ci-4nvu6&region=local_v2
*/

//题解代码: 
class Solution {
public:
    #define ll long long
    vector<long long> findMaxSum(vector<int>& nums1, vector<int>& nums2, int k) {
      int n = nums1.size();
      vector<ll> ans(n);
        vector<pair<int,int>> a(n);
        for(int i=0;i<n;++i){
            a[i].first = nums1[i];
            a[i].second = i;
        }
        sort(a.begin(),a.end(),[&](const pair<int,int>& p1,const pair<int,int>& p2)->bool{
             return p1.first < p2.first;
        });
        priority_queue<int,vector<int>,greater<int>> pq;
        ll sum = 0;
        for(int i=0,j=0;i<n;++i){
            int num = a[i].first,idx = a[i].second;
            while(a[j].first<a[i].first){
                sum += nums2[a[j].second];
                pq.push(nums2[a[j].second]);
                ++j;
            }
            while(pq.size()>k){
                sum -= pq.top();
                pq.pop();
            }
            ans[idx] = sum;
        }
        return ans;
    }
};
